package union;

import jdk.nashorn.internal.ir.IfNode;

/**
 * @author kaho
 * @since 2020/12/17
 */
public class UNION_QUICK_RANK implements UNION{

    int[] parent;
    int[] rank;

    public UNION_QUICK_RANK(int[] arr) {
        this.parent = arr;
        this.rank = new int[arr.length+1];
        for (int i = 0; i < arr.length; i++) {
            rank[i] = 1;
        }

    }

    @Override
    public int find(int v) {
        checkRange(v);
        while (parent[v]!=v){
            //路径分裂
            parent[v] = parent[parent[v]];
            v = parent[v];
        }
        return v;
    }

    @Override
    public void union(int v1, int v2) {
        int p1 = find(v1);
        int p2 = find(v2);
        if (p1 == p2) {
            return;
        }
        //基于rank优化
        if (rank[p1] < rank[p2]) {
            parent[p1] = p2;
        }else if(rank[p1] > rank[p2]){
            parent[p2] = p1;
        }else {
            parent[p1] = p2;
            rank[p2]++;
        }
    }

    @Override
    public boolean isSame(int v1, int v2) {
        return parent[v1] == parent[v2];
    }

    @Override
    public void checkRange(int v) {
        if(v>parent.length-1){
            throw new IndexOutOfBoundsException("");
        }
    }
}
